package DP;

/**
 * https://www.lintcode.com/problem/unique-paths-ii/description
 */
public class UniquePath2 {
    /**
     * 几个注意点：
     * 1.怎么取数组的宽高，这个居然给忘了。 先取宽是否0，非0，就可以拿第一个来 看高度了。
     * 2.初始化的时候
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int weight = obstacleGrid.length;
        if(weight == 0){
            return 0;
        }

        int height = obstacleGrid[0].length;
        if(height == 0){
            return 0;
        }

        int[][] dp = new int[weight][height];

        for(int i=0; i < weight; i++){
            for(int j=0; j < height; j++){
                //如果是障碍，就要是0，然后，再判断是否第一行 或者 第一列
                if(obstacleGrid[i][j] == 1){
                    dp[i][j] = 0;
                    continue;
                }

                //初始状态 = 0
                if(i == 0 && j == 0){
                    dp[i][j] = 1;
                    continue;
                }

                dp[i][j] = 0;
                if(i > 0){
                    dp[i][j] += dp[i-1][j];
                }

                if(j > 0){
                    dp[i][j] += dp[i][j-1];
                }
            }
        }

        return dp[weight-1][height-1];
    }



    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }


}
